package prac8;
/**
 * Generic list data type implemented as an abstract linked list.
 * 
 * @author          Maria Garcia de la Banda
 * @modified        Brendon Taylor (Feb 2010) - JavaDoc
 *                  Brendon Taylor (Feb 2010) - JavaDoc
 *                  Maria (March 2011) - Hierarchy + Interfaces
 * @param           <T> type of element to be stored in this list
 * @since           July 2006
 * @modified        March 2011
 * @input           none
 * @output          only for regression testing
 * @errorHandling   none
 * @knownBugs       none
 */

/*
 * Invariants:
 *   (1) head points to the first node in the list, or null if empty
 *   (2) each node points to the next node in the position in the list
 *   (2) last points to the last node in the list
 */
public abstract class LinkedList<T> implements List<T> {
    /** reference to the first node, null if empty */
    protected Node head; 
    /** marks the last node, null if empty */
    protected Node last; 
    /** represents the length of the list */
    protected int length;
    
    /**
     * Implements each linked node, 
     * defined as protected since only descendant classes need to access it.
     * 
     * @author    Maria Garcia de la Banda
     * @modified  Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
     *            Brendon Taylor (Feb 2010) - JavaDoc
     */
    protected class Node {   
        /** polymorphic data in the node */
        protected T item;
        /** reference to the successor node */
        protected Node successor;

        /**
         * Creates a new node of the list wit the appropriate data.
         *
         * @param newItem to be stored in this node
         * @param newSuccessor reference to the successor node in the list
         * @post  a node object is created with data newItem and linked to 
         *        newSuccessor
         * @complexity  best and worst case: O(1)
         */
        protected Node(T newItem, Node newSuccessor) {
            item = newItem;
            successor = newSuccessor;
        }

    }

    /**
     * Implements a list iterator.
     * 
     * @author    Maria Garcia de la Banda
     * @modified  Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
     */
    
    /*
     * Invariants:
     *  (1) current points to either a node in the list or to null
        (2) if there exists a node in the list such that node.successor = current
     *      then previous points to that node. Otherwise it is null.
     */
    protected class MyIterator implements Iterator<T> {
        /** points to the successor node the user can use */
        protected Node current;
        /** points to the node used previously by the user */
        protected Node previous;

        /**
         * Creates an initial object for the class, i.e., an iterator for the
         * list where current points to head (and thus, previous to null, 
         * considering the invariant for the class).
         * 
         * @post        current points to head
         * @complexity  best and worst case: O(1)
         */
        protected MyIterator() {
            current = head;
            previous = null;
        }

         /**
         * Determines whether the iterator has gone through all items
         * already, or there are some left to iterate.
         * 
         * @post        the list is unchanged
         * @return      true if there is an element that has not yet
         *              been iterated over, false otherwise 
         * @complexity  best and worst case: O(1)
         */
        public boolean hasNext() {
            return (current != null);
        }

        /**
         * Resets the iterator to its initial state.
         * 
         * @post        current points to the head (and thus previous to null)
         * @complexity  best and worst case: O(1)
         */
        public void reset() {
            current = head;
            previous = null;
        }

        /**
         * Returns the element that is about to be iterated over 
         * If none left, it throws a NoSuchElementException.
         * 
         * @return      element at the current position 
         * @post        the list is unchanged
         * @post        the element that is about to be iterated over 
         *              or throws NoSuchElementException if none left
         * @complexity  best and worst case: O(1)            
         */
        public T peek() {
            if (hasNext())
                    return current.item;
        
            throw new NoSuchElementException("at peek()");
        }

        /**
         * Returns the next element that has not been processed and moves to 
         * next one. If all nodes had already been iterated over, it throws
         * a NoSuchElementException
         * 
         * @return      the next element to be processed
         * @post        the list is unchanged
         * @post        if there is an element that has not yet been iterated
         *              over, it returns it and moves over it. Otherwise 
         *              it throws NoSuchElementException.
         * @complexity  best and worst case: O(1)  
         */
        public T next() {
            if (hasNext()) {
                    previous = current;
                    current = current.successor;
                    return previous.item;
            }

            throw new NoSuchElementException("at next()");
        }

        /**
         * Deletes the element that was next to be processed and moves to the
         * next. If all nodes had already been iterated over, it throws 
         * a NoSuchElementException
         * 
         * @post        if there is an element that has not yet been iterated
         *              over, it deletes it and moves over it. Otherwise 
         *              it throws NoSuchElementException.
         * @post        contains exactly the same elements as before, except
         *              for the element that was about to be iterated over.
         * @complexity  best and worst case: O(1) 
         */
        public void deleteHere() { 
            if (hasNext()) {
                    if (previous == null) // first element
                            head = head.successor;
                    else                 // not first
                            previous.successor = current.successor;

                    if (current == last) //last element
                            last = previous;
                    current = current.successor;
                    length--;
            }
            else {
                    throw new NoSuchElementException("at deleteHere()");
            }
        }        

        // Note that the iterator does not contain an addHere(T newItem) 
        // method, since it could be problematic for a sorted list. 
    }

    /**
     * Called by descendant classed to initialise the common instance variables.
     *
     * @post        the variables are set as for an  empty list object
     * @complexity  best and worst case: O(1) 
     */
    public LinkedList() {
        head = null;
        last = null;
        length = 0;
    }

    /**
     * Used to check whether the list is empty.
     * 
     * @return      Succeeds if the list is empty
     * @complexity  best and worst case: O(1) 
     */
    public boolean isEmpty() {
        return (head == null);
    }

    /**
     * Used to check whether the list is full (it never is)
     * Method introduced for consistency with the list implemented with arrays.
     * 
     * @return              false
     * @post        returns false 
     * @complexity  best and worst case: O(1) 
     */
    public boolean isFull() {
        return false;
    }

    /**
     * Resets the list to an empty state.
     * 
     * @post        the list is empty
     * @complexity  best and worst case: O(1) 
     */
    public void clear() {
        head = null;
        last = null;
        length = 0;
    }

    /**
     * Creates a new iterator for the list.
     * 
     * @return      new abstract list iterator
     * @see         Iterator#Iterator()
     */
    public Iterator<T> iterator() {
        return new MyIterator();
    }

    /**
     * Achieved by iterating through the list until the object is found or the
     * end of the list is reached.
     * 
     * @param       thisItem to search for in this list 
     * @return      returns null if the item does not appear in the list,
     *              otherwise, the address of the first node the item appears in.
     * @complexity  if equals is O(M) where M is the size of T, then best
     *              case O(M) when thisItem is the first, worst O(N*M) when
     *              it does not find it, where N is the length of the list  
     */
    public boolean find(T thisItem) {  
        Iterator<T> i = this.iterator();
        while (i.hasNext()) {
                if (i.next().equals(thisItem))
                        return true;
        }
        
        return false;
    } 

    /**
     * Add a new item to this list.
     * 
     * @param       newItem to add to this list
     * @post        the item will appear in the list. Where? it will depend on
     *              the particular concrete class
     */
    public abstract void add(T newItem);

    /**
     * The first element in the list is eliminated from the list and returned.
     * 
     * @return      the first element in the list
     * @pre         the list is not empty
     * @post        the first element in the list is eliminated from the list
     *              and returned it,careful resetting last if the list becomes empty
     * @complexity  best and worst case O(1): fixed number of iterations
     */
    public T deleteFirst() {
        if (isEmpty()) {
                throw new EmptyListException("at deleteFirst()");}
        else {
                if (head == last) // only one element
                        last = null;
                T temp = head.item;
                head = head.successor;
                length--;
                return temp;
        }
    }

    /**
     * The last element in the list is eliminated from the list and returned.
     * 
     * @return      the last element in the list
     * @pre         the list is not empty
     * @complexity  Best and worst case O(N): where N is the length of the 
     *              list, since it traverses the entire list performing a 
     *              fixed number of operations 
     */
    public T deleteLast() {
        if (isEmpty()) {
                throw new EmptyListException("at deleteLast()");
        }
        
        T temp = last.item;
	if (head.successor == null) {//only one element
	    head = null; last = null;
	} else {                  //more than one
	    Node current = head.successor;
	    Node previous = head;
	    while (current.successor != null) {
		previous = current;
		current = current.successor;
	    }
	    previous.successor = null;
	    last = previous;
	}
	return temp;
    }

    /**
     * Removes thisItem from the list (if exists).
     * 
     * @return      if thisItem appears in the list, it eliminates its first 
     *              occurrence and returns true. Otherwise it returns false.
     * @param               thisItem to be deleted
     * @complexity  if equals is O(M) where M is the size of T, then best
     *              case O(M) when thisItem is the first, worst O(N*M) when
     *              it does not find it, where N is the length of the list
     */
    public boolean deleteItem(T thisItem) {
        Iterator<T> i = this.iterator();
        while (i.hasNext())
        {
                if (i.peek().equals(thisItem))
                {
                        i.deleteHere();
                        return true;
                }
                else 
                        i.next();
        }

        return false;
    } 

    /**
     * @return      length of this list
     * @complexity  best and worse case: O(1)
     */
    public int size() {
            return length;
    }
    
    /**
     * Converts this list to a String.
     * 
     * @return              a string which represents all the elements in the list
     * @complexity  Best and worst case: O(N) where N is the length of the list
     */
    public String toString() {
        String temp = "";
        Iterator<T> i = this.iterator();
        while(i.hasNext())
                temp += " " + i.next();
        
        return temp;
    }

    /**
     * Compares two lists to see whether they are equal.
     * 
     * @param       otherO to compare with 
     * @return      true if the two lists contain the same elements
     *              in the same order
     * @complexity  best and worse case: if equals is O(M) where M is the size of T, 
     *              then O(N*M), where N is the length of the list
     */
    @SuppressWarnings("unchecked")
    public boolean equals(Object otherO) {
        if (otherO == null || getClass()!=otherO.getClass())
                return false;
        
        LinkedList<T> otherL = (LinkedList<T>)otherO;
        Iterator<T> thisI = this.iterator();
        Iterator<T> otherI = otherL.iterator();
    
        while (thisI.hasNext() && otherI.hasNext())
        {  
                if (!thisI.next().equals(otherI.next()))
                        return false;
        }

        return (!thisI.hasNext() & !otherI.hasNext());
    }
}       

